package me.doublysentinel;

import java.util.Iterator;
import java.util.function.Consumer;

public class DoublyLinkedListSentinel implements Iterable<Integer> {
    // 节点类
    public static class Node {
        Node prev; // 上一个节点指针
        int value; // 值
        Node next; // 下一个节点指针

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    // 记录链表元素数量
    private int size = 0;

    private Node head; // 头哨兵
    private Node tail; // 尾哨兵

    // 构造方法初始化头尾哨兵
    public DoublyLinkedListSentinel() {
        head = new Node(null, 666, null);
        tail = new Node(null, 888, null);
        head.next = tail;
        tail.prev = head;
    }

    // 1.通过索引找到节点
    private Node findNode(int index) {
        int i = -1; // -1代表头哨兵节点的索引
        for (Node p = head; p != tail; p = p.next, i++) {
            if (i == index) {
                return p;
            }
        }
        return null;
    }

    // 2.头插
    public void addFirst(int value) {
        insert(0, value);
        size++;
    }

    // 3.头删
    public void removeFirst() {
        remove(0);
        size--;
    }

    // 4.尾插
    public void addLast(int value) {
        // 原链表的最后一个节点
        Node last = tail.prev;
        Node added = new Node(last, value, tail);
        last.next = added;
        tail.prev = added;

        size++;
    }

    // 5.尾删
    public void removeLast() {
        // 待删除的节点
        Node removed = tail.prev;
        if (removed == head) {
            throw illegalIndex(0);
        }
        Node prev = removed.prev;
        prev.next = tail;
        tail.prev = prev;

        size--;
    }

    // 6.任意位置插入
    public void insert(int index, int value) {
        // 待插入节点的上一节点
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw illegalIndex(index);
        }
        // 待插入节点的下一节点
        Node next = prev.next;
        Node inserted = new Node(prev, value, next);
        prev.next = inserted;
        next.prev = inserted;

        size++;
    }

    // 7.任意位置删除
    public void remove(int index) {
        // 待删除节点的上一节点
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw illegalIndex(index);
        }
        Node removed = prev.next;
        if (removed == tail) {
            throw illegalIndex(index);
        }
        Node next = removed.next;
        prev.next = next;
        next.prev = prev;

        size--;
    }

    // 8.异常抛出
    private static IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(
                String.format("index [%d] 不合法%n", index));
    }

    // 9.迭代器遍历
    @Override
    public Iterator<Integer> iterator() {
        //匿名内部类
        return new Iterator<Integer>() {
            // 从头哨兵的下一节点开始
            Node p = head.next;

            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    // 10.consumer遍历，让外部决定做什么
    public void loop1(Consumer<Integer> consumer) {
        Node p = head.next;
        while (p != tail) {
            consumer.accept(p.value);
            p = p.next;
        }
    }

    // 11.打印链表
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node p = head.next;
        while (p != tail) {
            sb.append(p.value).append(" -> ");
            p = p.next;
        }
        sb.append("null");
        return sb.toString();
    }
}
